1. Field of the Invention
The present invention relates to a method of and an apparatus for determining adjoining relationships between a plurality of image parts. The present invention also relates to a method of and an apparatus for processing image data which include parts data representing a plurality of image parts that are drawn in a predefined drawing order while determining adjoining relationships between the plurality of image parts.
2. Description of the Related Art
In the field of prepress processing, one image generally consists of a plurality of image parts. When two image parts are located adjacent to each other, an overlapping area (also referred to as a `trapping area` or an `overlaying area`) is formed on a boundary between the adjoining image parts, in order to prevent a dropout from being observed on the boundary.
In order to generate a trapping area, it is required first to determine which pair of image parts among the plurality of image parts adjoin to each other. The expression `image parts adjoining to each other` means that the image parts are in close contact with each other without any clearance on at least part of the boundary between the image parts, or they overlap each other at least partially.
FIGS. 13A-13C show a known method of determining adjoining relationships between a plurality of image parts. In the conventional process of determining an adjoining relationship between two image parts shown in FIG. 13A, it is first determined whether the circumscribed rectangles of the respective image parts shown by the broken lines in FIG. 13B overlap each other. When the circumscribed rectangles overlap each other, the two image parts may adjoin to each other. It is then determined whether vectors representing the contours of the respective image parts cross each other as shown in FIG. 13C. When the contour vectors cross each other or partially overlap each other, the two image parts are determined to adjoin to each other. It is here assumed that one general image consists of N image parts and that the contour of each image part consists of `n` vectors. The processing time required for determining the overlapping relationships between the respective pairs of circumscribed rectangles of the N image parts is in proportion to the number N of the image parts. The processing time required for determining whether the contour vectors of the two image parts cross each other is in proportion to the second power of the number `n` of the contour vectors. Namely the total processing time required for extracting all the possible combinations of two image parts from the N image parts and determining whether the contour vectors cross each other for all the possible combinations is expected to be substantially in proportion to n.sup.2 .times.N.sup.2.
In the conventional method discussed above, as the number N of the image parts or the number n of the vectors constituting the contour vector of each image part increases, the required processing time remarkably increases in proportion to the second power of the increased number. An extremely long time is required for the processing especially when the number N of image parts is as large as tens or hundreds of thousands.
Incidentally, in DTP (desktop publishing) applications using a computer system, a group of consecutive figures having a fixed rate of density variation sometimes creates an image area having a substantially continuous gradation in density. This group of consecutive figures is generally referred to as a `blend`, `blend figure` or `color step`. Although each figure included in the blend figure represents one individual figure, the group of figures is drawn to generate an image area having a substantially continuous change in density.
In some cases, it is necessary to form a trapping area on a boundary between a blend figure and another image part. Image data (for example, a page description language such as PostScript (trademark of Adobe Corporation)), however, do not include information indicating that the image part is part of the blend figure. In the conventional method, the trapping process is accordingly carried out between each image part included in the blend figure and another image part not included in the blend figure. This undesirably increases the processing time required for creating a trapping area. This problem is not characteristic of the trapping process but is found in a variety of image processing operations with respect to the blend figure.